package com.org.hw.algorithm.string;

import java.util.*;

/**
 * @Program: demo
 * @Author: hewei
 * @Date: 2024-03-19 10:37
 * @Description:
 * 中缀表达式：3+4*5-6/3
 * 后缀表达式（逆波兰表达式）：3 4 5 * + 6 3 / -
 **/
public class PostfixExpression {
    /*公共栈，存放数值和符号，用来转化中缀表达式*/
    private static Stack<String> commonStack = new Stack<>();
    /*原始表达式字符读取指针*/
    private static int index = 0;
    /*字符类别*/
    private static final String OPER ="operator";//四则运算符
    private static final String NUM ="number"; //数值
    private static final String BRAC ="bracket"; //括号
    /*运算符和对应的优先级,括号不属于运算符，所以给了最低的优先级，这样运算符可以正常放入栈中的括号上*/
    private static Map<String, Integer> operLevel = new HashMap<>() {{
        put("+", 0);
        put("-", 0);
        put("*", 1);
        put("/", 1);
        put("(", -1);
        put(")", -1);
    }};

    /*运算控制符：括号*/
    private static List<String> brackets = Arrays.asList("(",")");

    /**
     * 后缀表达式的计算
     * 1、从左至右按顺序遍历后缀表达式，遇到数值直接入栈，遇到运算符则从栈中弹出两个数与符号进行运算，并将结果再压入栈
     * 2、一直往复执行第 1 部，直到表达式完毕
     * 3、最终栈中的数值就是计算结果，弹出即可
     * 
     * @param postfixExpress 后缀表达式
     * @param separator 表达式元素分隔符
     * */
    public static Integer caculate(String postfixExpress, String separator) throws Exception {
        commonStack.clear();
        List<String> expList = Arrays.asList(postfixExpress.split(separator));
        for (String exp : expList) {
            if (operLevel.containsKey(exp)) {
                Integer num2 = Integer.valueOf(commonStack.pop());
                Integer num1 = Integer.valueOf(commonStack.pop());
                commonStack.push(getResult(num1,num2,exp).toString());
            }else {
                commonStack.push(exp);
            }
        }
        return Integer.valueOf(commonStack.pop());
    }

    /**
     * 读取中缀表达式中的多位数的数字字符串和运算符
     * 1、逐个读取数字字符进行连接，直到遇到操作符才停止
     * 2、每读取一位符号同时将 index 指针后移一位
     * */
    private static Map<String,String> getElement(String expression) {

        /*如果当前是括号直接返回，并且指针 index 后移一位*/
        if (brackets.contains(String.valueOf(expression.charAt(index)))) {
            return Map.of(BRAC,String.valueOf(expression.charAt(index++)));
        }
        /*如果当前是操作符则直接返回，并且 index 后移一位*/
        if (operLevel.containsKey(String.valueOf(expression.charAt(index)))) {
            return Map.of(OPER,String.valueOf(expression.charAt(index++)));
        }
        /*读取数字字符,每读取一位 index 后移一位*/
        StringBuilder sb = new StringBuilder();
        for (; index < expression.length(); index++) {
            String c = String.valueOf(expression.charAt(index));
            if (operLevel.containsKey(c)) {
                break;
            }
            sb.append(c);
        }
        return Map.of(NUM, sb.toString());
    }

    /**
     * 将中缀表达式转换成后缀表达式：
     *
     * 一、初始化一个空的字符串（用于存储转换后的后缀表达式，暂时称其为结果字符串）和一个栈（用于暂时存储运算符）。
     *
     * 二、从左到右遍历中缀表达式的每一个数字和符号。
     *
     *  1、若当前字符为数字，则直接将其放入结果字符串尾部，成为后缀表达式的一部分。
     *  2、若当前字符为运算符，则需要进行以下判断和处理：
     *      （1）若栈为空，直接将该运算符压入栈中。
     *      （2）若读取的运算符优先级高于栈顶的运算符，则将该运算符压入栈中。（这里的优先级判断通常遵循乘除优先于加减的原则）
     *      （3）若读取的运算符优先级低于或等于栈顶的运算符，则从栈顶弹出运算符并追加到结果字符串尾部。并将当前符号入栈。
     *      （4）若读取的运算符为左括号，也直接压入栈中。
     *      （5）若读取的运算符为右括号，不需要入栈，从栈顶开始逐个弹出运算符并追加到结果字符串尾部，直到遇见栈顶为左括号（左括号需要出栈，但不放入字符串中）。
     *
     * 三、当遍历完中缀表达式的所有数字和符号后，若栈中还有剩余的运算符，则依次将它们弹出并追加到结果字符串尾部。
     *
     * 温馨提示：每次往初始化字符串尾部添加内容时建议同时添加一个分割符（建议空格），以便区分数值，否则数值可能串联。例如 11 和 95，拼接时可能成为 1195。
     *
     * @param express 原始的中缀表达式
     * @param separator 返回的结果表达式中元素的分隔符
     * */
    private static String parsePostfix(String express,String separator) {
        /*字符串指针初始化到开始位置*/
        index = 0;
        /*除去字符串中的空白字符，包括空格，tab，换行*/
        String source = express.replaceAll("\\s","");
        int len = source.length();
        StringBuilder result=new StringBuilder();
        while (index < len) {
            Map<String, String> operMap = getElement(source);
            /*如果是数值则直接追加到结果字符串尾部*/
            if (operMap.containsKey(NUM)) {
                result.append(separator+operMap.get(NUM));
                continue;
            }
            /*如果栈为空，任何符号直接入栈*/
            if (commonStack.empty()) {
                commonStack.push(operMap.values().stream().findFirst().get());
                continue;
            }
            /*如果是运算符号执行以下操作*/
            if (operMap.containsKey(OPER)){
                String op = operMap.get(OPER);
                /*如果 [当前运算符优先级 > 栈栈顶符号的优先级]直接压入栈*/
                if (operLevel.get(op) > operLevel.get(commonStack.peek())){
                    commonStack.push(op);
                    continue;
                /*如果 [当前运算符优先级 <= 栈顶符号优先级],则弹出栈顶符号追加到结果字符串尾部，然后将当前符号入栈*/
                }else{
                    result.append(separator+commonStack.pop());
                    commonStack.push(op);
                    continue;
                }
            }
            /*如果是括号执行以下操作*/
            if (operMap.containsKey(BRAC)) {
                /* 如果是 左括号 "(" 直接压入栈 */
                if ("(".equals(operMap.get(BRAC))) {
                    commonStack.push("(");
                    continue;
                /* 如果是 右括号 ")" 不需要入栈,需要逐个弹出栈中的符号元素添加到结果字符串尾部，直到遇到 "(" 为止，并弹左括号 */
                }else if (")".equals(operMap.get(BRAC))){
                    while (!"(".equals(commonStack.peek())) {
                        result.append(separator+commonStack.pop());
                    }
                    commonStack.pop();
                    continue;
                }
            }
        }
        /*如果原始字符串遍历完毕，栈中还有剩余符号，逐个弹出追加到结果字符串尾部*/
        while (!commonStack.isEmpty()) {
            result.append(separator+commonStack.pop());
        }
        return result.toString();
    }
    /**
     * 计算单步操作的结果
     * num1 前置操作数
     * num2 后置操作数
     * oper 运算符
     * */
    private static Integer getResult(Integer num1, Integer num2, String oper) throws Exception {
        switch (oper) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "/":
                return num1 / num2;
            case "*":
                return num1 * num2;
            default:
                throw new Exception("无效操作符");
        }
    }

    /**
     * 人为将中缀表达式转换为后缀表达式的方法：
     * 1、按照运算优先级给所有运算单元添加括号（）
     * 2、当前将括号中运算单元的运算符移至括号右侧（前缀表达式将符号移至括号左侧）
     * 3、去除所有括号
     * 实例：3+4*5-6/3
     * （1）3+(4*5)-(6/3)
     * （2）(3+(4*5))-(6/3)  => ((3+(4*5))-(6/3))
     * （3）(3+(4*5))(6/3)-
     * （4）(3(4*5))+(6 3)/ -
     * （5）(3(4 5)*)+(6 3)/-
     * （6）3 4 5 * + 6 3 / -
     * */
    public static void main(String[] args) {
        /* 3+4-5 */
//        String postfixExpress = "3 4 + 5 -";
        /* 3+4*5-6/3 */
//        String postfixExpress = "3 4 5 * + 6 3 / -";
        /**
         * 3+(4*5-5)/3
         * (3+(((4*5)-5)/3))
         * (3(((4 5)*5)-3)/)+
         * 3 4 5 * 5 - 3 / +
         * */
        String postfixExpress = " ";
        try {
            System.out.println(PostfixExpression.caculate(postfixExpress," "));
            postfixExpress=parsePostfix("3+(4*5-5)/3"," ");
            System.out.println(postfixExpress);
            System.out.println(PostfixExpression.caculate(postfixExpress," "));

        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}